解題程式碼

var RandomizedSet = function () {
  this.indexMap = new Map();
  this.values = [];
};

RandomizedSet.prototype.insert = function (val) {
  if (this.indexMap.has(val)) return false;

  this.values.push(val);
  this.indexMap.set(val, this.values.length - 1);
  return true;
};

RandomizedSet.prototype.remove = function (val) {
  if (!this.indexMap.has(val)) return false;

  const index = this.indexMap.get(val);
  this.indexMap.delete(val);
  const lastEle = this.values.pop();

  // this.values.length 不需要 -1，因為已經 pop 出一個元素
  // 檢查是否是取到最後一個元素索引，不是的話將最後一個元素取代當前要刪除的元素
  if (index !== this.values.length) {
    this.values[index] = lastEle;
    this.indexMap.set(lastEle, index);
  }

  return true;
};

RandomizedSet.prototype.getRandom = function () {
  const randomIndex = Math.floor(Math.random() * this.values.length);
  return this.values[randomIndex];
};

解題思路、演算法

hashMap 和陣列的結合運用。

陣列可以以 O(1) 的時間複雜度隨機取元素出來，也可以以相同的時間複雜度加入元素，但如果要移除指定元素，會需要 O(n)。

所以使用 hashMap 去加速查找元素，hashMap 去記錄元素值和在陣列的索引，就可以以 O(1) 的時間複雜度移除指定元素。

解法的時間、空間複雜度

時間複雜度: 三個函式都是 O(1)
空間複雜度: O(n)

參考資料

Insert Delete GetRandom O(1) - Leetcode 380 - Python